#pragma once

#include<string>
#include<vector>
#include<iostream>
#include<utility>

using namespace std;

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

//为了测试提前写的KeyOfT
template<class K, class T>
struct KeyOfT
{
	const K& operator()(const T& data)
	{
		return data.first;
	}
};

namespace CloseHash
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class T>
	struct HashData
	{
		T _data;
		Status _status = EMPTY;
	};

	template<class K, class T, class KeyOfT, class HashFun = Hash<K>>
	class HashTable
	{
	public:
		bool Insert(const T& data)
		{
			KeyOfT kot;
			HashFun hs;

			//判断是否需要扩容
			if (_tables.size() == 0 || _size * 10 / _tables.size() >= 7)
			{
				size_t newSize = _size == 0 ? 10 : 2 * _tables.size();
				HashTable<K, T, KeyOfT, HashFun> newHash;
				newHash._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHash.Insert(_tables[i]._data);
					}

				}
				_tables.swap(newHash._tables);
				newHash._size = _size;
			}

			size_t start = hs(kot(data)) % _tables.size();
			int i = 1;
			while (_tables[start]._status == EXIST)
			{
				if (_tables[start]._data == data)
				{
					return false;
				}
				start = start + i * i;
				start %= _tables.size();
				i++;
			}
			_tables[start]._data = data;
			_tables[start]._status = EXIST;
			_size++;
			return true;
		}
		
		bool Erase(const T& data)
		{
			KeyOfT kot;
			HashFun hs;
			size_t start = hs(kot(data)) % _tables.size();
			int i = 0;
			while (_tables[start]._status == EXIST)
			{
				if (_tables[start]._data == data)
				{
					_tables[start]._status = DELETE;
					return true;
				}
				start = start + i * i;
				start %= _tables.size();
				i++;
			}
			//不存在
			return false;
		}
		
		HashData<T>* find(const T& data)
		{
			KeyOfT kot;
			HashFun hs;
			size_t start = hs(kot(data)) % _tables.size();
			int i = 0;
			while (_tables[start]._status == EXIST)
			{
				if (_tables[start]._data == data)
				{
					return &_tables[start];
				}
				start = start + i * i;
				start %= _tables.size();
				i++;
			}
			return nullptr;
		}
	private:
		vector<HashData<T>> _tables;
		size_t _size = 0;
	};

	void test1()
	{
		//T:pair<int, string>
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>> hs;
		hs.Insert(make_pair(1, "one"));
		hs.Insert(make_pair(11, "one"));
		hs.Insert(make_pair(12, "two"));
		hs.Insert(make_pair(23, "three"));
		hs.Insert(make_pair(62, "two"));
		hs.Insert(make_pair(63, "three"));
		hs.Insert(make_pair(22, "two"));
		hs.Insert(make_pair(71, "one"));
		hs.Insert(make_pair(62, "two"));
		hs.Insert(make_pair(21, "one"));
		hs.Insert(make_pair(43, "three"));
		hs.Insert(make_pair(3, "three"));
		hs.Insert(make_pair(41, "one"));
		hs.Insert(make_pair(82, "two"));
		hs.Insert(make_pair(3, "three"));
		hs.Insert(make_pair(53, "three"));
		HashData<pair<int, string>>*  ptr = hs.find(make_pair(53, "three"));
		bool ret = hs.Erase(make_pair(53, "three"));
		ptr = hs.find(make_pair(53, "three"));
		ret = hs.Erase(make_pair(53, "three"));
	}
}

namespace LinkHash
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			: _data(data)
			, _next(nullptr)
		{}
	};

	//前置声明，解决相互应用的问题
	template<class K, class T, class KeyOfT, class HashFun>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFun>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, HashFun> HTable;
		typedef HTIterator<K, T, Ref, Ptr, KeyOfT, HashFun> Self;

		// 核心成员变量
		HashNode<T>* _node;
		HTable* _ptr; // 存一个指向哈希表的指针

        // 成员函数
		HTIterator(Node* node, HTable* ptr)
			: _node(node)
			, _ptr(ptr)
		{}

		//operator++() 可以返回自己的引用。
		Self& operator++()
		{
			KeyOfT kot;
			HashFun hf;

			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				//计算自己所在的桶
				size_t start = hf(kot(_node->_data)) % _ptr->_tables.size();
				//找下一个不为空的桶
				size_t i = start + 1;
				while (i < _ptr->_tables.size())
				{
					if (_ptr->_tables[i])
						break;

					i++;
				}

				//走到头也没有找到不为空的桶
				if (i == _ptr->_tables.size())
					_node = nullptr;
				else
					_node = _ptr->_tables[i];

			}

			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		bool operator!=(Self right)
		{
			return _node != right._node;
		}

		bool operator==(Self right)
		{
			return _node == right._node;
		}
	};

	template<class K, class T, class KeyOfT, class HashFun = Hash<K>>
	class HashTable
	{
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFun = Hash<K>>
		friend struct HTIterator;

		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, HashFun> Self;

	public:
		typedef HTIterator<K, T, T&, T*, KeyOfT, HashFun> iterator;
		typedef HTIterator<K, T, const T&, const T*, KeyOfT, HashFun> const_iterator;

		////默认构造1
		//HashTable()
		//{}

		//默认构造2
		//显示指定编译器去生成默认构造函数
		HashTable() = default;

		//拷贝构造
		HashTable(const Self& ht)
		{
			_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); i++)
			{			
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					copy->_next = _tables[i];
					_tables[i] = copy;
					_size++;
					cur = cur->_next;
				}
			
			}
		}
		//赋值操作符重载
		Self& operator=(Self tmp)
		{
			_tables.swap(tmp._tables);
			::swap(_size, tmp._size);
			return *this;
		}
		//析构
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				Node* next = nullptr;				
				while (cur)
				{
					next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Insert(const T& data)
		{
			KeyOfT kot;
			HashFun hf;

			//判断是否需要扩容
			if (_tables.size() == _size)
			{
				//开始扩容
				size_t sz = _tables.size() == 0 ? 10 : _tables.size() * 2;
				Self newHash;
				newHash._tables.resize(sz);

				size_t i = 0;
				while (i < _tables.size())
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHash.Insert(cur->_data);
						cur = cur->_next;
					}
					i++;
				}
				_tables.swap(newHash._tables);
			}
			//开始插入
			Node* newNode = new Node(data);
			size_t start = hf(kot(data)) % _tables.size();
			Node* cur = _tables[start];
			Node* prev = nullptr;

			while (cur)
			{
				//判断是否有相等元素
				if (cur->_data == data)
					return false;

				prev = cur;
				cur = cur->_next;
			}

			newNode->_next = _tables[start];
			_tables[start] = newNode;
			_size++;
			return true;
		}
		////Erase 法一 
		//bool Erase(const T& data) 附：//Erase传参应该是K，而不是T，故此处需修改但是原理与逻辑不变
		//{
		//	for (int i = 0; i < _tables.size(); i++)
		//	{
		//		Node* cur = _tables[i];
		//		Node* prev = nullptr;
		//		while (cur)
		//		{
		//			if (cur->_data == data)
		//			{
		//				if (prev == nullptr)
		//				{
		//					//头删
		//					_tables[i] = cur->_next;
		//				}
		//				else
		//				{
		//					prev->_next = cur->_next;
		//				}
		// 
		//				_size--;
		//				delete cur;
		//				return true;
		//			}
		//			prev = cur;
		//			cur = cur->_next;
		//		}
		//	}
		//	return false;
		//}
		
		//Erase 法二
		//bool Erase(const T& data) //Erase传参应该是K，而不是T
		bool Erase(const K& key)
		{
			if (_tables.empty())
			{
				return false;
			}

			HashFun hf;
			KeyOfT kot;
			size_t start = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[start];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr) // 头删
					{
						_tables[start] = cur->_next;
					}
					else // 中间删除
					{
						prev->_next = cur->_next;
					}
			 
					_size--;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		iterator Find(const K& key)
		{
			HashFun hs;
			KeyOfT kot;

			size_t start = hs(key) % _tables.size();
			Node* cur = _tables[start];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}
				cur = cur->_next;
			}
			return end();

		}

		iterator begin()
		{
			//return _tables[0];--->错误写法，要先找到不为空的桶
			size_t i = 0;
			while (i < _tables.size())
			{
				if (_tables[i])
					return iterator(_tables[i], this);

				i++;
			}
			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}
		
	private:
		vector<Node*> _tables;
		size_t _size = 0;
	};
	void test1()
	{
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>> hs;
		hs.Insert(make_pair(1, "one"));
		hs.Insert(make_pair(11, "one"));
		hs.Insert(make_pair(12, "two"));
		hs.Insert(make_pair(23, "three"));
		hs.Insert(make_pair(62, "two"));
		hs.Insert(make_pair(63, "three"));
		hs.Insert(make_pair(22, "two"));
		hs.Insert(make_pair(71, "one"));
		hs.Insert(make_pair(62, "two"));
		hs.Insert(make_pair(21, "one"));
		hs.Insert(make_pair(43, "three"));
		hs.Insert(make_pair(3, "three"));
		hs.Insert(make_pair(41, "one"));
		hs.Insert(make_pair(82, "two"));
		hs.Insert(make_pair(3, "three"));
		hs.Insert(make_pair(53, "three"));

		

		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>, Hash<int>>::iterator it = hs.begin();
		while (it != hs.end())
		{
			cout << (*it).first << "--->" << (*it).second << " ";
			++it;
		}
		cout << endl;
		//拷贝构造验证
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>, Hash<int>> hs1(hs);
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>, Hash<int>>::iterator it1 = hs1.begin();
		while (it1 != hs1.end())
		{
			cout << (*it1).first << "--->" << (*it1).second << " ";
			++it1;
		}
		cout << endl;
		//赋值操作符重载验证
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>, Hash<int>> hs2;
		hs2 = hs1;
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>, Hash<int>>::iterator it2 = hs2.begin();
		while (it2 != hs2.end())
		{
			cout << (*it2).first << "--->" << (*it2).second << " ";
			++it2;
		}
		cout << endl;

		it = hs.Find(41);
		bool ret = hs.Erase(41);
		it = hs.Find(41);
		ret = hs.Erase(41);
		ret = hs.Erase(21);


	}
}